template <typename T>
class UnionFindSet
{
public:
    UnionFindSet()
    {
    }

    template <typename TContainer>
    UnionFindSet(const TContainer &container)
    {
        auto begin = container.begin();
        auto end = container.end();
        while (begin != end)
        {
            m[*begin] = *begin;
            ++begin;
            ++_groupCount;
        }
    }

    void insert(const T &value)
    {
        if (!m.count(value))
        {
            m[value] = value;
            ++_groupCount;
        }
    }

    bool exist(const T &value)
    {
        return m.count(value);
    }

    T find(const T &value)
    {
        if (m[value] == value)
        {
            return value;
        }
        return m[value] = find(m[value]);
    }

    void join(const T &value1, const T &value2)
    {
        if (find(value1) != find(value2))
        {
            m[find(value1)] = find(value2);
            --_groupCount;
        }
    }

    int groupCount()
    {
        return _groupCount;
    }

private:
    std::unordered_map<T, T> m;
    int _groupCount = 0;
};

class Solution
{
public:
    // 对集合进行拓扑排序，复杂度O(mn) (可能再乘log(mn))
    vector<vector<int>> matrixRankTransform(vector<vector<int>> &matrix)
    {
        int m = matrix.size();
        int n = matrix[0].size();
        int size = m * n;

        auto index2dTo1d = [&](int x, int y)
        {
            return x + y * m;
        };

        auto index1dTo2d = [&](int i)
        {
            return array<int, 2>{i % m, i / m};
        };

        UnionFindSet<int> equalRankGroups;
        for (int i = 0; i < size; ++i)
        {
            equalRankGroups.insert(i);
        }

        // 分别按行和按列对索引排序
        // 先处理秩相等的元素

        vector<vector<int>> rowSortedMatrixColIndex(m);
        for (int row = 0; row < m; ++row)
        {
            auto &rowSortedColIndex = rowSortedMatrixColIndex[row];
            rowSortedColIndex = vector<int>(n);
            iota(rowSortedColIndex.begin(), rowSortedColIndex.end(), 0);
            auto compare = [&](int i, int j)
            {
                return matrix[row][i] < matrix[row][j];
            };
            sort(rowSortedColIndex.begin(), rowSortedColIndex.end(), compare);

            for (int j = 1; j < n; ++j)
            {
                int col1 = rowSortedColIndex[j - 1];
                int col2 = rowSortedColIndex[j];
                if (matrix[row][col1] == matrix[row][col2])
                {
                    equalRankGroups.join(index2dTo1d(row, col1), index2dTo1d(row, col2));
                }
            }
        }

        vector<vector<int>> colSortedMatrixRowIndex(n);
        for (int col = 0; col < n; ++col)
        {
            auto &colSortedRowIndex = colSortedMatrixRowIndex[col];
            colSortedRowIndex = vector<int>(m);
            iota(colSortedRowIndex.begin(), colSortedRowIndex.end(), 0);
            auto compare = [&](int i, int j)
            {
                return matrix[i][col] < matrix[j][col];
            };
            sort(colSortedRowIndex.begin(), colSortedRowIndex.end(), compare);

            for (int j = 1; j < m; ++j)
            {
                int row1 = colSortedRowIndex[j - 1];
                int row2 = colSortedRowIndex[j];
                if (matrix[row1][col] == matrix[row2][col])
                {
                    equalRankGroups.join(index2dTo1d(row1, col), index2dTo1d(row2, col));
                }
            }
        }

        // 再处理秩不等的元素
        // 在秩相等的集合之间建立有向图

        unordered_map<int, int> equalRankGroupInDegree;

        for (int i = 0; i < size; ++i)
        {
            equalRankGroupInDegree[equalRankGroups.find(i)] = 0;
        }

        unordered_map<int, unordered_set<int>> outEdges;
        for (int row = 0; row < m; ++row)
        {
            auto &rowSortedColIndex = rowSortedMatrixColIndex[row];
            for (int j = 1; j < n; ++j)
            {
                int col1 = rowSortedColIndex[j - 1];
                int col2 = rowSortedColIndex[j];

                if (matrix[row][col1] < matrix[row][col2])
                {
                    int outGroup = equalRankGroups.find(index2dTo1d(row, col1));
                    int inGroup = equalRankGroups.find(index2dTo1d(row, col2));
                    if (!outEdges[outGroup].count(inGroup))
                    {
                        outEdges[outGroup].insert(inGroup);
                        ++equalRankGroupInDegree[inGroup];
                    }
                }
            }
        }

        for (int col = 0; col < n; ++col)
        {
            auto &colSortedRowIndex = colSortedMatrixRowIndex[col];
            for (int j = 1; j < m; ++j)
            {
                int row1 = colSortedRowIndex[j - 1];
                int row2 = colSortedRowIndex[j];
                if (matrix[row1][col] < matrix[row2][col])
                {
                    int outGroup = equalRankGroups.find(index2dTo1d(row1, col));
                    int inGroup = equalRankGroups.find(index2dTo1d(row2, col));
                    if (!outEdges[outGroup].count(inGroup))
                    {
                        outEdges[outGroup].insert(inGroup);
                        ++equalRankGroupInDegree[inGroup];
                    }
                }
            }
        }

        // 对集合进行拓扑排序，无需考虑集合中的具体元素

        unordered_map<int, int> groupRanks;
        queue<int> q;

        for (auto &[i, inDegree] : equalRankGroupInDegree)
        {
            auto [x, y] = index1dTo2d(i);
            if (inDegree == 0)
            {
                groupRanks[i] = 1;
                q.push(i);
            }
        }

        while (!q.empty())
        {
            int i = q.front();
            q.pop();
            for (auto nextI : outEdges[i])
            {
                groupRanks[nextI] = max(groupRanks[nextI], groupRanks[i] + 1);
                --equalRankGroupInDegree[nextI];
                if (equalRankGroupInDegree[nextI] == 0)
                {
                    q.push(nextI);
                }
            }
        }

        vector<vector<int>> result(m, vector<int>(n));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                result[i][j] = groupRanks[equalRankGroups.find(index2dTo1d(i, j))];
            }
        }
        return result;
    }

    // 对所有元素进行拓扑排序，应该是对的，但是复杂度 O((mn)^2)，会超时
    vector<vector<int>> matrixRankTransform(vector<vector<int>> &matrix)
    {
        int m = matrix.size();
        int n = matrix[0].size();
        int size = m * n;
        unordered_map<int, int> inDegree;
        unordered_map<int, vector<int>> outEdges;
        UnionFindSet<int> equalRankGroups;

        for (int i = 0; i < size; ++i)
        {
            equalRankGroups.insert(i);
            inDegree[i] = 0;
        }

        auto index2dTo1d = [&](int x, int y)
        {
            return x + y * m;
        };

        auto index1dTo2d = [&](int i)
        {
            return array<int, 2>{i % m, i / m};
        };

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                for (int x = i + 1; x < m; ++x)
                {
                    if (matrix[i][j] == matrix[x][j])
                    {
                        equalRankGroups.join(index2dTo1d(i, j), index2dTo1d(x, j));
                    }
                    else if (matrix[i][j] > matrix[x][j])
                    {
                        outEdges[index2dTo1d(x, j)].push_back(index2dTo1d(i, j));
                        ++inDegree[index2dTo1d(i, j)];
                    }
                    else
                    {
                        outEdges[index2dTo1d(i, j)].push_back(index2dTo1d(x, j));
                        ++inDegree[index2dTo1d(x, j)];
                    }
                }
                for (int y = j + 1; y < n; ++y)
                {
                    if (matrix[i][j] == matrix[i][y])
                    {
                        equalRankGroups.join(index2dTo1d(i, j), index2dTo1d(i, y));
                    }
                    else if (matrix[i][j] > matrix[i][y])
                    {
                        outEdges[index2dTo1d(i, y)].push_back(index2dTo1d(i, j));
                        ++inDegree[index2dTo1d(i, j)];
                    }
                    else
                    {
                        outEdges[index2dTo1d(i, j)].push_back(index2dTo1d(i, y));
                        ++inDegree[index2dTo1d(i, y)];
                    }
                }
            }
        }

        // 直接对所有元素拓扑排序，只有当元素及其同秩集合的所有元素的入度均为0，才能拎出来
        // 复杂度较高
        int rank = 1;
        vector<vector<int>> result(m, vector<int>(n));
        while (true)
        {
            unordered_map<int, int> maxGroupInDegree;
            for (auto [i, inDeg] : inDegree)
            {
                maxGroupInDegree[equalRankGroups.find(i)] = max(maxGroupInDegree[equalRankGroups.find(i)], inDeg);
            }

            unordered_set<int> zeroInDegreeElements;
            for (auto [i, inDeg] : inDegree)
            {
                if (inDeg == 0 && maxGroupInDegree[equalRankGroups.find(i)] == 0)
                {
                    zeroInDegreeElements.insert(i);
                }
            }

            if (zeroInDegreeElements.empty())
            {
                break;
            }

            for (int e : zeroInDegreeElements)
            {
                inDegree.erase(e);
                auto [x, y] = index1dTo2d(e);
                result[x][y] = rank;
                for (auto greaterElement : outEdges[e])
                {
                    --inDegree[greaterElement];
                }
            }

            ++rank;
        }
        return result;
    }
};